﻿using System.Collections.Generic;
using System;

namespace ProjectEuler
{
    internal class Problem14
    {
        Dictionary<long, int> chainLengths = new Dictionary<long, int>();
        private int maxLength;
        private long starter;

        public void Solve()
        {
            chainLengths[1] = 1;
            chainLengths[2] = 2;

            var len13 = GetChainLen(13);
            Console.WriteLine("len 13: " + len13);

            for (var i = 3; i < 1000000; i++)
            {
                var len = GetChainLen(i);
                if (maxLength < len)
                {
                    maxLength = len;
                    starter = i;
                }
                //Console.WriteLine("starting " + i+ " length = " + len);
            }

            Console.WriteLine("problem 14: starter = " + starter + " maxlen = " + maxLength);
        }

        int GetChainLen(long num)
        {
            int len = 0;
            long currNum = num;

            if (chainLengths.ContainsKey(num)) return chainLengths[num];

            while ((currNum = Next(currNum)) != 1)
            {
                len++;

                if (chainLengths.ContainsKey(currNum))
                {
                    len += chainLengths[currNum];
                    break;
                }
            }

            return len;
        }

        long Next(long num)
        {
            return num%2 == 0 ? num/2 : 3*num + 1;
        }
    }
}